import heapq
from typing import List
from collections import deque


class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        grid00 = grid[0][0]
        grid[0][0] = 0
        n = len(grid)
        inf = n * n
        s = 0
        t = n * n - 1
        d = [inf] * (n * n)
        d[s] = 0
        q = [(d[s], s)]
        while q:
            du, u = heapq.heappop(q)
            if du > d[u]:
                continue
            if u == t:
                return max(du, grid00)
            row, col = u // n, u % n
            up = row - 1, col
            down = row + 1, col
            left = row, col - 1
            right = row, col + 1
            for row1, col1 in [up, down, left, right]:
                if not (0 <= row1 < n and 0 <= col1 < n):
                    continue
                v = row1 * n + col1
                alt = max(grid[row1][col1], d[u])
                if alt < d[v]:
                    d[v] = alt
                    heapq.heappush(q, (d[v], v))


class BrutalSolution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)

        def bfs(time):
            n = len(grid)
            inf = n * n
            s = 0
            t = n * n - 1
            d = [inf] * (n * n)
            d[s] = 0
            q = deque([s])
            while q:
                u = q.popleft()
                if u == t:
                    return True
                row, col = u // n, u % n
                up = row - 1, col
                down = row + 1, col
                left = row, col - 1
                right = row, col + 1
                for row1, col1 in [up, down, left, right]:
                    if not (0 <= row1 < n and 0 <= col1 < n):
                        continue
                    v = row1 * n + col1
                    if grid[row1][col1] > time:
                        continue
                    if d[v] == inf:
                        d[v] = d[u] + 1
                        q.append(v)
            return False

        for time in range(n * n):
            if bfs(time):
                return time


solution = Solution()
brutal_solution = BrutalSolution()
from copy import deepcopy
def test():
    cases = [
        (
            [[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]],
            16
        ),
        (
            [[0, 3], [2, 1]],
            2
        ),
        (
            [[0]],
            0
        ),
        (
            [[3, 0], [1, 2]],
            3
        )
    ]
    for question, answer in cases:
        assert solution.swimInWater(deepcopy(question)) == answer
test()


def random_test():
    import random
    random.seed(1)
    for case_num in range(10000):
        n = random.randint(1, 6)
        nums = list(range(1, n * n))
        random.shuffle(nums)
        nums = [0] + nums
        grid = [[] for _ in range(n)]
        for row in range(n):
            for col in range(n):
                grid[row].append(nums[row * n + col])

        is_same = solution.swimInWater(deepcopy(grid)) == brutal_solution.swimInWater(deepcopy(grid))
        if not is_same:
            print(grid)
        # assert is_same
# random_test()
